package MySort;

/**
 * 215. 数组中的第K个最大元素
 *
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 *
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 *
 * 说明:
 */

import java.io.Closeable;
import java.util.PriorityQueue;

/**
 * 快排 找第k个最大的数
 */
public class Leetcode215 {
    // 方法1 堆排序
    public static int findKthLargest1(int[] nums, int k) {
        // 大顶堆
        // PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) ->(o2 -o1));
        // 这里用默认的小顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for(int num : nums){
            heap.offer(num);
            if(heap.size() > k){
                heap.poll();
            }
        }
        return heap.peek();
    }

    public static int findKthLargest(int[] nums, int k) {
        return Qsort(nums, 0, nums.length-1, nums.length-k);
    }

    // 方法2 快排
    // 所以只要某次划分的 p 为倒数第 k 个下标的时候，我们就已经找到了答案。
    public static int Qsort(int[] arr, int start, int end, int index) {

        if (start < end) {
            // 哨兵
            int stand = arr[start];
            int low = start;
            int high = end;

            while (low < high) {
                while (low < high && arr[high] > stand) {
                    high--;
                }
                arr[low] = arr[high];

                while (low < high && arr[low] < stand) {
                    low++;
                }
                arr[high] = arr[low];
            }
            arr[low] = stand;
            if(low == index){
                return low;
            }

            Qsort(arr, start, low, index);
            Qsort(arr, low + 1, end, index);
        }
        return start;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{1,3,5,4,6,3,32,8};
        int kthLargest1 = findKthLargest(nums, 4);
        System.out.println(kthLargest1);
    }

}
